{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Apply Operations to Make Two Strings Equal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minOperations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #执行操作使两个字符串相等"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个下标从 <strong>0</strong>&nbsp;开始的二进制字符串&nbsp;<code>s1</code> 和&nbsp;<code>s2</code>&nbsp;，两个字符串的长度都是&nbsp;<code>n</code>&nbsp;，再给你一个正整数&nbsp;<code>x</code>&nbsp;。</p>\n",
    "\n",
    "<p>你可以对字符串 <code>s1</code>&nbsp;执行以下操作 <strong>任意次</strong>&nbsp;：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选择两个下标&nbsp;<code>i</code>&nbsp;和&nbsp;<code>j</code>&nbsp;，将&nbsp;<code>s1[i]</code> 和&nbsp;<code>s1[j]</code>&nbsp;都反转，操作的代价为&nbsp;<code>x</code>&nbsp;。</li>\n",
    "\t<li>选择满足 <code>i &lt; n - 1</code>&nbsp;的下标&nbsp;<code>i</code>&nbsp;，反转&nbsp;<code>s1[i]</code> 和&nbsp;<code>s1[i + 1]</code>&nbsp;，操作的代价为&nbsp;<code>1</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回使字符串&nbsp;<code>s1</code>&nbsp;和&nbsp;<code>s2</code>&nbsp;相等的&nbsp;<strong>最小</strong>&nbsp;操作代价之和，如果无法让二者相等，返回&nbsp;<code>-1</code>&nbsp;。</p>\n",
    "\n",
    "<p><strong>注意</strong>&nbsp;，反转字符的意思是将&nbsp;<code>0</code>&nbsp;变成&nbsp;<code>1</code>&nbsp;，或者 <code>1</code>&nbsp;变成 <code>0</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s1 = \"1100011000\", s2 = \"0101001010\", x = 2\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>我们可以执行以下操作：\n",
    "- 选择 i = 3 执行第二个操作。结果字符串是 s1 = \"110<em><strong>11</strong></em>11000\" 。\n",
    "- 选择 i = 4 执行第二个操作。结果字符串是 s1 = \"1101<em><strong>00</strong></em>1000\" 。\n",
    "- 选择 i = 0 和 j = 8 ，执行第一个操作。结果字符串是 s1 = \"<em><strong>0</strong></em>1010010<em><strong>1</strong></em>0\" = s2 。\n",
    "总代价是 1 + 1 + 2 = 4 。这是最小代价和。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s1 = \"10110\", s2 = \"00011\", x = 4\n",
    "<b>输出：</b>-1\n",
    "<b>解释：</b>无法使两个字符串相等。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == s1.length == s2.length</code></li>\n",
    "\t<li><code>1 &lt;= n, x &lt;= 500</code></li>\n",
    "\t<li><code>s1</code> 和&nbsp;<code>s2</code>&nbsp;只包含字符&nbsp;<code>'0'</code> 和&nbsp;<code>'1'</code> 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [apply-operations-to-make-two-strings-equal](https://leetcode.cn/problems/apply-operations-to-make-two-strings-equal/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [apply-operations-to-make-two-strings-equal](https://leetcode.cn/problems/apply-operations-to-make-two-strings-equal/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"1100011000\"\\n\"0101001010\"\\n2', '\"10110\"\\n\"00011\"\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        \n",
    "        cands = [i for i in range(len(s1)) if s1[i] != s2[i]]\n",
    "        \n",
    "        n = len(cands)\n",
    "        \n",
    "        if n % 2: return -1\n",
    "        \n",
    "        @cache\n",
    "        def dp(i, j):\n",
    "            if i > j:\n",
    "                return 0\n",
    "\n",
    "            # if cands[i+1] - cands[i] < cands[j] - cands[j-1]:               \n",
    "            #     return min(cands[i+1] - cands[i] + dp(i+2, j), x + dp(i+1, j-1))\n",
    "            # else:\n",
    "            return min(cands[j] - cands[j-1] + dp(i, j-2), cands[i+1] - cands[i] + dp(i+2, j), x + dp(i+1, j-1))\n",
    "        \n",
    "        \n",
    "        return dp(0, n-1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        if s1 == s2:\n",
    "            return 0\n",
    "        p = [i for i, (x, y) in enumerate(zip(s1, s2)) if x != y]\n",
    "        if len(p) % 2:\n",
    "            return -1\n",
    "        f0, f1 = 0, x\n",
    "        for i, j in pairwise(p):\n",
    "            f0, f1 = f1, min(f1 + x, f0 + (j - i) * 2)\n",
    "        return f1 // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        cnt1 = Counter(s1)\n",
    "        cnt2 = Counter(s2)\n",
    "        if (cnt2['1'] - cnt1['1']) % 2 != 0:\n",
    "            return -1\n",
    "        \n",
    "        tmp = []\n",
    "        for i, (c1, c2) in enumerate(zip(s1, s2)):\n",
    "            if c1 != c2:\n",
    "                tmp.append(i)\n",
    "        \n",
    "        # dp2: \n",
    "        # dp0: 表示该数字结尾，下一个跟他用距离结算\n",
    "        # dp1: 下一个跟前面的某一个用x结算, 还没结算完成\n",
    "        \n",
    "        # dp0 结束\n",
    "        # dp1 还没结束\n",
    "        \n",
    "        if not tmp:\n",
    "            return 0\n",
    "        \n",
    "        dp0 = min(tmp[1] - tmp[0], x)\n",
    "        dp1 = 0\n",
    "        for i in range(2, len(tmp), 2):\n",
    "            dp0, dp1 = min(dp1 + min(tmp[i] - tmp[i-1], x) + x, dp0 + min(tmp[i+1] - tmp[i], x)), min(dp0, dp1 + min(tmp[i] - tmp[i-1], x))\n",
    "        return dp0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.x = 0\n",
    "        self.diff = []\n",
    "        self.INT_MAX = 2 ** 31\n",
    "\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        self.x = x\n",
    "        n: int = len(s1)\n",
    "        # 记录需要操作的下标的位置\n",
    "        diff = []\n",
    "        for i in range(n):\n",
    "            if s1[i] != s2[i]:\n",
    "                diff.append(i)\n",
    "        self.diff = diff\n",
    "\n",
    "        m: int = len(diff)\n",
    "        if m == 0:\n",
    "            return 0\n",
    "        if m % 2 == 1:\n",
    "            return -1\n",
    "\n",
    "        return int(self.dfs(m - 1))\n",
    "\n",
    "    # 记忆化搜索\n",
    "    # n: 还剩余多少字符需要处理\n",
    "    @cache\n",
    "    def dfs(self, n: int) -> int:\n",
    "        if n == -2:\n",
    "            return self.INT_MAX\n",
    "        if n == -1:\n",
    "            return 0\n",
    "        # 进行第一种操作\n",
    "        a = self.dfs(n - 1) + self.x / 2\n",
    "        # 进行第二种操作\n",
    "        b = self.dfs(n - 2) + self.diff[n] - self.diff[n - 1]\n",
    "        return min(a, b)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "\n",
    "        t = list()\n",
    "        for i in range(len(s1)):\n",
    "            if s1[i] != s2[i]:\n",
    "                t.append(i)\n",
    "\n",
    "        # print(len(l))\n",
    "        # 奇数个要反转的一定不可能\n",
    "        if len(t) & 1 == 1:\n",
    "            return -1\n",
    "\n",
    "        # 本质上是两两合并代价最小\n",
    "\n",
    "        n = len(t)\n",
    "\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        for l in range(2, n+1, 2):\n",
    "            for i in range(n-l+1):\n",
    "                j = i + l - 1\n",
    "                dp[i][j] = dp[i+1][j-1] + min(x, t[j]-t[i])\n",
    "                if i + 2 < n: \n",
    "                    dp[i][j] = min(dp[i][j], min(x, t[i+1]-t[i])+dp[i+2][j])\n",
    "                if j - 2 > -1:\n",
    "                    dp[i][j] = min(dp[i][j], min(x, t[j]-t[j-1])+dp[i][j-2])\n",
    "\n",
    "                # for k in range(i+1, j, 2):\n",
    "                #     dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j])\n",
    "\n",
    "        return dp[0][n-1] if n > 0 else 0\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # # ---------------------暴力方法会超时啊--------------------------------\n",
    "        # 剪枝\n",
    "        # l = list()\n",
    "        # for i in range(len(s1)):\n",
    "        #     if s1[i] != s2[i]:\n",
    "        #         l.append(i)\n",
    "\n",
    "        # # print(len(l))\n",
    "        # # 奇数个要反转的一定不可能\n",
    "        # if len(l) & 1 == 1:\n",
    "        #     return -1\n",
    "        # min_s = 1e9\n",
    "\n",
    "        # v = [0]*len(l)\n",
    "        # @cache\n",
    "        # def cost(n, c):\n",
    "        #     nonlocal min_s, v\n",
    "\n",
    "        #     if n == len(l):\n",
    "        #         min_s = min(min_s, c)\n",
    "        #         # print(c)\n",
    "        #     else:\n",
    "        #         for i in range(len(l)):\n",
    "        #             if v[i] == 0:\n",
    "        #                 v[i] = 1\n",
    "        #                 for j in range(i+1, len(l)):\n",
    "        #                     if v[j] == 0:\n",
    "        #                         v[j] = 1\n",
    "        #                         cost(n+2, c + min(x, l[j]-l[i]))\n",
    "        #                         v[j] = 0\n",
    "        #                 v[i] = 0\n",
    "\n",
    "        # cost(0, 0)\n",
    "\n",
    "        # return min_s\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        n = len(s1)\n",
    "        diffs = []\n",
    "        for i in range(n):\n",
    "            if s1[i] != s2[i]:\n",
    "                diffs.append(i)\n",
    "        \n",
    "        ndiff = len(diffs)\n",
    "        if ndiff == 0:\n",
    "            return 0\n",
    "        if ndiff % 2 != 0:\n",
    "            return -1\n",
    "        \n",
    "        dp = [[-1]*ndiff for _ in range(ndiff)]\n",
    "        for i in range(ndiff-1):\n",
    "            dp[i][i+1] = min(x, diffs[i+1] - diffs[i])\n",
    "        # print(diffs)\n",
    "        def calc_dp(i, j):\n",
    "            if dp[i][j] != -1:\n",
    "                return dp[i][j]\n",
    "            \n",
    "            a1 = calc_dp(i+1,j-1) + x\n",
    "            a2 = calc_dp(i+2,j) + diffs[i+1]-diffs[i]\n",
    "            a3 = calc_dp(i,j-2) + diffs[j]-diffs[j-1]\n",
    "            dp[i][j] = min(a1, a2, a3)\n",
    "            return dp[i][j]\n",
    "\n",
    "        sol = calc_dp(0, ndiff-1)\n",
    "        return sol\n",
    "\n",
    "# print(Solution().minOperations(\"100010010100111100001110101111100001001101011010100111101011100100011111110001011001001\", \"000001100010010011111101100101111011101110010001001010100101011100011110000111010011010\", 6))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        n = len(s1)\n",
    "        a = []\n",
    "        for i in range(n):\n",
    "            if s1[i] != s2[i]:\n",
    "                a.append(i)\n",
    "                \n",
    "        if len(a) % 2 == 1:\n",
    "            return -1\n",
    "\n",
    "        n = len(a)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "    \n",
    "        f = [[10000000] * (n + 1) for i in range(n + 1)]\n",
    "        for i in range(n):\n",
    "            j = i + 1\n",
    "            if j >= n:\n",
    "                continue\n",
    "            f[i][j] = min(a[j] - a[i], x)\n",
    "        for d in range(3, n + 1):\n",
    "            for l in range(0, n):\n",
    "                if d == 1:\n",
    "                    f[l][l] = 10000000\n",
    "                r = l + d - 1\n",
    "                if r >= n:\n",
    "                    continue\n",
    "                f[l][r] = min([f[l + 2][r] + a[l + 1] - a[l], f[l][r - 2] + a[r] - a[r - 1], f[l + 1][r - 1] + min(a[r] - a[l], x)])\n",
    "\n",
    "        \n",
    "        return f[0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        n=len(s1)\n",
    "        ls=[]\n",
    "        for i in range(n):\n",
    "            if s1[i]!=s2[i]:\n",
    "                ls.append(i)\n",
    "        if len(ls)%2==1:\n",
    "            return -1\n",
    "        to_change=ls\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def deal(pt=0, end=len(to_change)) :\n",
    "            if pt >= end :\n",
    "                return 0\n",
    "            to_ret = deal(pt+2, end) + (to_change[pt+1]-to_change[pt])\n",
    "            if to_change[pt+1]-to_change[pt] == 1 :\n",
    "                return to_ret\n",
    "            \n",
    "            for pnext in range(pt+1, end, 2) :\n",
    "                rett = deal(pt+1, pnext) + deal(pnext+1, end) + x\n",
    "                to_ret = min(to_ret, rett)\n",
    "            return to_ret\n",
    "        return deal()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        pos = [i for i in range(len(s1)) if s1[i] != s2[i]]\n",
    "        n = len(pos)\n",
    "        if n % 2:\n",
    "            return -1\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(l, r):\n",
    "            if l >= r:\n",
    "                return 0\n",
    "\n",
    "            a = min(x, pos[r] - pos[l]) + dfs(l + 1, r - 1)\n",
    "            b = min(x, pos[l + 1] - pos[l]) + dfs(l + 2, r)\n",
    "            c = min(x, pos[r] - pos[r - 1]) + dfs(l, r - 2)\n",
    "            return min(a, b, c)\n",
    "\n",
    "        ans = dfs(0, n - 1)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        pos = [i for i in range(len(s1)) if s1[i] != s2[i]]\n",
    "        n = len(pos)\n",
    "        if n % 2:\n",
    "            return -1\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(l, r):\n",
    "            if l >= r:\n",
    "                return 0\n",
    "\n",
    "            a = min(x, pos[r] - pos[l]) + dfs(l + 1, r - 1)\n",
    "            b = min(x, pos[l + 1] - pos[l]) + dfs(l + 2, r)\n",
    "            c = min(x, pos[r] - pos[r - 1]) + dfs(l, r - 2)\n",
    "            return min(a, b, c)\n",
    "\n",
    "        ans = dfs(0, n - 1)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        n = len(s1)\n",
    "        li = [] \n",
    "        for i in range(n):\n",
    "            if s1[i]!=s2[i]:\n",
    "                li.append(i)\n",
    "        m = len(li)\n",
    "        if m%2:\n",
    "            return -1 \n",
    "        if m==0:\n",
    "            return 0\n",
    "        \n",
    "        @cache \n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i==j-1:\n",
    "                return min(li[j]-li[i], x)\n",
    "            ans = x+dfs(i+1, j-1)\n",
    "            k = 1\n",
    "            while i+k+1<j:\n",
    "                ans = min(ans, dfs(i, i+k) + dfs(i+k+1, j))\n",
    "                k += 2\n",
    "            return ans \n",
    "        \n",
    "        return dfs(0, m-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        loc = []\n",
    "        for i in range(len(s1)):\n",
    "            if(s1[i] != s2[i]):\n",
    "                loc.append(i)\n",
    "        if(len(loc) % 2 == 1):\n",
    "            return -1\n",
    "\n",
    "        self.dic = {}\n",
    "        def cal(start, end):\n",
    "            if(start >= end):\n",
    "                return 0\n",
    "            if((start, end) in self.dic):\n",
    "                return self.dic[(start, end)]\n",
    "            if(start + 1 == end):\n",
    "                if(loc[end] - loc[start] < x):\n",
    "                    ans = loc[end] - loc[start]\n",
    "                else:\n",
    "                    ans = x\n",
    "            else:\n",
    "                res = []\n",
    "                j = start + 1\n",
    "                while(j <= end):\n",
    "                    if(loc[j] - loc[start] < x):\n",
    "                        ans = loc[j] - loc[start]\n",
    "                    else:\n",
    "                        ans = x\n",
    "                    temp = ans + cal(start + 1, j - 1) + cal(j+1, end)\n",
    "                    res.append(temp)\n",
    "                    j += 2\n",
    "                ans = min(res)\n",
    "            self.dic[(start, end)] = ans\n",
    "            return ans\n",
    "\n",
    "        return cal(0, len(loc)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        n = len(s1)\n",
    "        lt = []\n",
    "        for i in range(n):\n",
    "            if s1[i] != s2[i]:\n",
    "                lt.append(i)\n",
    "        m = len(lt)\n",
    "        if m % 2 == 1:\n",
    "            return -1\n",
    "        print(lt)\n",
    "        \n",
    "        @functools.cache\n",
    "        def dfs(p, q):\n",
    "            if p > q:\n",
    "                return 0\n",
    "            return min(x + dfs(p + 1, q - 1), min(x, lt[p + 1] - lt[p]) + dfs(p + 2, q), min(x, lt[q] - lt[q - 1]) + dfs(p, q - 2))\n",
    "        \n",
    "        return dfs(0, m - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        if s1 == s2: return 0\n",
    "        pos = [i for i in range(len(s1)) if s1[i] != s2[i]]\n",
    "        n = len(pos)\n",
    "        if n % 2: return -1\n",
    "        @cache\n",
    "        def dfs(l, r):\n",
    "            if l >= r: return 0\n",
    "            a = pos[l + 1] - pos[l] + dfs(l + 2, r)\n",
    "            b = x + dfs(l + 1, r - 1)\n",
    "            c = pos[r] - pos[r - 1] + dfs(l, r - 2)\n",
    "            return min(a, b, c)\n",
    "\n",
    "        return dfs(0, n - 1)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        n = len(s1)\n",
    "        arr = []\n",
    "        for i in range(n):\n",
    "            if s1[i] != s2[i]:\n",
    "                arr.append(i)\n",
    "        if len(arr) % 2 == 1:\n",
    "            return -1\n",
    "        \n",
    "        ## 统计差异点，差异点必须两两交换\n",
    "        ## 贪心思路 操作一 只适合相邻的差异点\n",
    "        ## 操作二 增加一个计数用于统计前面使用过的次数\n",
    "        @cache\n",
    "        def dfs(i, c):\n",
    "            if i < 0:\n",
    "                return inf if c else 0\n",
    "            res = dfs(i-1, c+1) + x\n",
    "            if i:\n",
    "                res = min(res, dfs(i-2, c) + arr[i] - arr[i-1])\n",
    "            if c:\n",
    "                res = min(res, dfs(i-1, c-1))\n",
    "            return res\n",
    "        \n",
    "        return dfs(len(arr)-1, 0)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        n = len(s1)\n",
    "        a = [i for i in range(n) if s1[i] != s2[i]]\n",
    "        m = len(a)\n",
    "        if m % 2:\n",
    "            return -1\n",
    "\n",
    "        @cache\n",
    "        def g(p, q):\n",
    "            if p > q:\n",
    "                return 0\n",
    "            if p == q:\n",
    "                return math.inf\n",
    "            if p == m-1:\n",
    "                return math.inf\n",
    "            ans = a[p+1] - a[p] + g(p+2, q)\n",
    "            if a[p+1] == a[p]+1:\n",
    "                return ans\n",
    "            for k in range(p+1, q+1):\n",
    "                ans = min(ans, x + g(p+1, k-1) + g(k+1, q))\n",
    "            return ans\n",
    "        \n",
    "        ans = g(0, m-1)\n",
    "        return ans if ans < math.inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        res = [i for i in range(len(s1)) if s1[i] != s2[i]]\n",
    "        if len(res) % 2 == 1:\n",
    "            return -1\n",
    "        \n",
    "        cache = {}\n",
    "\n",
    "        def dp(left, right):\n",
    "            if f'{left}-{right}' in cache:\n",
    "                return cache[f'{left}-{right}']\n",
    "            if left > right:\n",
    "                return 0\n",
    "\n",
    "            a = dp(left + 1, right - 1) + min(x, res[right] - res[left])  # n***n\n",
    "            b = dp(left, right - 2) + min(x, res[right] - res[right - 1])  # n***nmm\n",
    "            c = dp(left + 2, right) + min(x, res[left + 1] - res[left])  # mmn***n\n",
    "            result = min(a, b, c)\n",
    "\n",
    "            cache[f'{left}-{right}'] = result\n",
    "            return result\n",
    "\n",
    "        return dp(0, len(res) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "import sys\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "'''\n",
    "\"100010010100111100001110101111100001001101011010100111101011100100011111110001011001001\"\n",
    "\"000001100010010011111101100101111011101110010001001010100101011100011110000111010011010\"\n",
    "6\n",
    "\n",
    "'''\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        arr = []\n",
    "        n = len(s1)\n",
    "        for i in range(n):\n",
    "            if s1[i] != s2[i]:\n",
    "                arr.append(i)\n",
    "\n",
    "        if len(arr) == 0:\n",
    "            return 0\n",
    "\n",
    "        if len(arr) % 2:\n",
    "            return -1\n",
    "\n",
    "        @lru_cache(typed=False, maxsize=128000000)\n",
    "        def dp(ii, jj):\n",
    "            if ii > jj:\n",
    "                return 0\n",
    "\n",
    "            val1 = (arr[ii+1]-arr[ii]) + dp(ii+2, jj)\n",
    "\n",
    "            val2 = 0x7f7f7f7f7f7f7f\n",
    "            for i in range(ii+1, jj+1, 2):\n",
    "                val2 = min(val2, x + dp(ii+1, i-1) + dp(i+1, jj))\n",
    "            return min(val1, val2)\n",
    "\n",
    "        return dp(0, len(arr)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        if sum(1 for i in range(len(s1)) if s1[i] != s2[i]) % 2 != 0:\n",
    "            return -1\n",
    "        n = len(s1)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, times, reverse=False):\n",
    "            if i == n:\n",
    "                if times != 0 or reverse:\n",
    "                    return x * n\n",
    "                return 0\n",
    "            if (s1[i] == s2[i]) != reverse:\n",
    "                return dfs(i + 1, times)\n",
    "            i += 1\n",
    "            res = min(1 + dfs(i, times, True), x + dfs(i, times + 1))\n",
    "            if times > 0:\n",
    "                res = min(res, dfs(i, times - 1))\n",
    "            return res\n",
    "\n",
    "        ans = dfs(0, 0)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "INF = int(1e18)\n",
    "\n",
    "\n",
    "def min(a: int, b: int) -> int:\n",
    "    return a if a < b else b\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(index: int, flip1Count: int, prevFlip2: bool) -> int:\n",
    "            if index == n:\n",
    "                return 0 if flip1Count == 0 else INF\n",
    "\n",
    "            cur = nums1[index] ^ prevFlip2\n",
    "            target = nums2[index]\n",
    "            if cur == target:\n",
    "                return dfs(index + 1, flip1Count, False)\n",
    "\n",
    "            # 反转1\n",
    "            res = dfs(index + 1, flip1Count + 1, False) + x\n",
    "            if flip1Count > 0:\n",
    "                res = min(res, dfs(index + 1, flip1Count - 1, False))\n",
    "            # 反转2\n",
    "            if index < n - 1:\n",
    "                res = min(res, dfs(index + 1, flip1Count, True) + 1)\n",
    "            return res\n",
    "\n",
    "        nums1 = [int(i) for i in s1]\n",
    "        nums2 = [int(i) for i in s2]\n",
    "        n = len(s1)\n",
    "        res = dfs(0, 0, False)\n",
    "        dfs.cache_clear()\n",
    "        return res if res < INF else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        if s1.count('1') % 2 != s2.count('1') % 2:\n",
    "            return -1\n",
    "        n = len(s1)\n",
    "        memoset = {}\n",
    "        def dfs(i, j, f):\n",
    "            if i >= n:\n",
    "                return inf if j > 0 or f else 0\n",
    "            if (i,j,f) in memoset:\n",
    "                return memoset[(i, j, f)]\n",
    "            cur = inf\n",
    "            if (s1[i] == s2[i]) == (not f):\n",
    "                return dfs(i+1, j, False)\n",
    "            cur = min(cur, dfs(i+1, j+1, False) + x, dfs(i+1, j, True) + 1)\n",
    "            if j:\n",
    "                cur = min(cur, dfs(i+1, j-1, False))\n",
    "            memoset[(i, j, f)] = cur\n",
    "            return cur\n",
    "        return dfs(0, 0, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        if s1.count('1') % 2 != s2.count('1') % 2:\n",
    "            return -1\n",
    "        n=len(s1)\n",
    "        # @cache\n",
    "        # def dfs(i: int, j: int , b) -> int:\n",
    "        #     if i < 0:\n",
    "        #         return inf if j or b else 0\n",
    "        #     if s1[i]==s2[i]:\n",
    "        #         if b:\n",
    "        #             return dfs(i - 1, j, True)+1  #相同且前面有则+1，没有则跳过\n",
    "        #         return dfs(i - 1, j, b)\n",
    "        #     if s1[i]!=s2[i]:        \n",
    "        #         if b:\n",
    "        #             return dfs(i - 1, j, False)  #不同且前面有，这次不算，没有得操作\n",
    "        #         res = min(dfs(i - 1, j + 1, b) + x, dfs(i - 1, j , True) + 1)\n",
    "        #     if j:  # 可以免费反转\n",
    "        #         res = min(res, dfs(i - 1, j - 1,b))\n",
    "        #     return res\n",
    "        # return dfs(len(s1) - 1, 0, False)\n",
    "        f=[[[0]*2 for _ in range(n+1)] for _ in range(n+1)]\n",
    "        for i in range(-1,n):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                for b in range(2):\n",
    "                    if i < 0:\n",
    "                        f[i][j][b]= inf if j or b else 0\n",
    "                        continue\n",
    "                    if s1[i]==s2[i]:\n",
    "                        if b:\n",
    "                            f[i][j][b] = f[i - 1][j][True]+1  #相同且前面有则+1，没有则跳过\n",
    "                            continue\n",
    "                        f[i][j][b] =f[i - 1][j][False]\n",
    "                        continue\n",
    "                    if s1[i]!=s2[i]:        \n",
    "                        if b:\n",
    "                            f[i][j][b]= f[i - 1][j][False]  #不同且前面有，这次不算，没有得操作\n",
    "                            continue\n",
    "                        f[i][j][b]= min(f[i - 1][j+1][b] + x, f[i - 1][j][True] + 1)\n",
    "                    if j:  # 可以免费反转\n",
    "                        f[i][j][b]= min(f[i][j][b], f[i - 1][j-1][b])\n",
    "        return f[n - 1][0][False]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        n=sum(x!=y for x,y in zip(s1,s2))\n",
    "        if n&1:return -1\n",
    "        a=[]\n",
    "        for i,(z,y) in enumerate(zip(s1,s2)):\n",
    "            if z!=y:\n",
    "                a.append(i)\n",
    "        @cache\n",
    "        def f(l,r):\n",
    "            if l>r:return 0\n",
    "            if r-l+1&1:return inf\n",
    "            ans=inf\n",
    "            for i in range(l+1,r+1):\n",
    "                d=a[i]-a[l]\n",
    "                if d>x:d=x\n",
    "                ans=min(ans,d+f(l+1,i-1)+f(i+1,r))\n",
    "            return ans\n",
    "        return f(0,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        \n",
    "        n = len(s1)\n",
    "        diff = []\n",
    "        for i in range(n):\n",
    "            if s1[i] != s2[i]: diff.append(i)\n",
    "        \n",
    "        if len(diff) % 2 == 1: return -1\n",
    "        m = len(diff)\n",
    "        if m == 0: return 0\n",
    "        @cache\n",
    "        def getans(i, j):\n",
    "            if i == j: return inf\n",
    "            if i+1 == j: return min(diff[j] - diff[i], x)            \n",
    "            ans = min(diff[j] - diff[i], x) + getans(i+1, j-1)\n",
    "            for k in range(i+1, j):\n",
    "                ans = min(ans, getans(i, k) + getans(k+1, j))\n",
    "            return ans\n",
    "        \n",
    "        return getans(0, m-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        if s1.count(\"1\") % 2 != s2.count(\"1\") % 2:\n",
    "            return -1\n",
    "        n = len(s1)\n",
    "        @cache\n",
    "        def dfs(i: int, j: int, pre: bool) -> int:\n",
    "            if j > i+1:\n",
    "                return inf\n",
    "            if i < 0:\n",
    "                return inf if j or pre else 0\n",
    "            if (s1[i] == s2[i]) == (not pre):\n",
    "                return dfs(i-1, j, False)\n",
    "            res = min(dfs(i-1, j+1, False) + x, dfs(i-1, j, True) + 1)\n",
    "            if j > 0:\n",
    "                res = min(res, dfs(i-1, j-1, False))\n",
    "            return res\n",
    "        return dfs(n-1, 0, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        n = len(s1)\n",
    "        d = []\n",
    "        for i in range(n):\n",
    "            if s1[i] != s2[i]:\n",
    "                d.append(i)\n",
    "                \n",
    "        if len(d) % 2 == 1:\n",
    "            return -1\n",
    "        \n",
    "        @cache\n",
    "        def dp(i, p, pre):\n",
    "            if i == len(d):\n",
    "                return p//2*x\n",
    "            if pre:\n",
    "                return min(min(d[i]-d[i-1], x) + dp(i+1, p-1, False), dp(i+1, p+1, True))\n",
    "            else:\n",
    "                return dp(i+1, p+1, True)\n",
    "        return dp(0, 0, False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1, s2, x):\n",
    "        s, t = list(s1), list(s2)\n",
    "        n, diff = len(s), 0\n",
    "        for i in range(n):\n",
    "            diff ^= ord(s[i]) ^ ord(t[i])\n",
    "        if diff != 0:\n",
    "            return -1\n",
    "        memo = [[[-1 for _ in range(2)] for _ in range(n + 1)] for _ in range(n)]\n",
    "\n",
    "        def dfs(i, j, preRev):\n",
    "            if i < 0:\n",
    "                return j > 0 or preRev > 0 and float('inf') or 0\n",
    "            if memo[i][j][preRev] != -1:\n",
    "                return memo[i][j][preRev]\n",
    "            if (s[i] == t[i]) == (preRev == 0):\n",
    "                return dfs(i - 1, j, 0)\n",
    "            res = min(dfs(i - 1, j + 1, 0) + x, dfs(i - 1, j, 1) + 1)\n",
    "            if j > 0:\n",
    "                res = min(res, dfs(i - 1, j - 1, 0))\n",
    "            memo[i][j][preRev] = res\n",
    "            return res\n",
    "\n",
    "        return dfs(n - 1, 0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        if s1.count(\"1\") % 2 != s2.count(\"1\") % 2:\n",
    "            return -1\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, j: int, preRev: bool) -> int:\n",
    "            if j > i > 0:\n",
    "                return math.inf\n",
    "            if i < 0:\n",
    "                # if j or preRev:  # 如果还能免费反转或者上一次进行了操作2，是不合法的\n",
    "                #     return math.inf\n",
    "                # return 0\n",
    "                return math.inf if j or preRev else 0\n",
    "            # if s1[i] == s2[i]:  # 如果该位置上两个一样，\n",
    "            #     if not preRev:  # 且上一次没有进行操作2\n",
    "            #         return dfs(i - 1, j, False)  # 带着一样的j直接进入下一个\n",
    "            # else :  # 如果该位置上两个不一样\n",
    "            #     if preRev:#但上一次进行了操作2，也就是该位置上已经反转\n",
    "            #         return dfs(i - 1, j, False)  # 也直接进入下一个\n",
    "            # 以上简写成：\n",
    "            if (s1[i] == s2[i]) == (not preRev):\n",
    "                return dfs(i - 1, j, False)\n",
    "\n",
    "            return min(dfs(i - 1, j, True) + 1,  # 采用操作2\n",
    "                       dfs(i - 1, j - 1, False) if j > 0 else math.inf,  # 免费反转\n",
    "                       dfs(i - 1, j + 1, False) + x,  # 采用操作1\n",
    "                       )\n",
    "\n",
    "        return dfs(len(s1) - 1, 0, False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        diff=[]\n",
    "        for i,tmp in enumerate(s1):\n",
    "            if tmp!=s2[i]:\n",
    "                diff.append(i)\n",
    "        l=len(diff)\n",
    "        if l==0:\n",
    "            return 0\n",
    "        if l%2!=0:\n",
    "            return -1\n",
    "        dp=[[[int(1e9),int(1e9)] for j in range(l+1)] for i in range(l)]\n",
    "        dp[0][1][1]=0\n",
    "        for i in range(1,l):\n",
    "            for j in range(i+2):\n",
    "                if j+1<l:\n",
    "                    dp[i][j][0]=min( dp[i][j][0] , dp[i-1][j+1][1]+diff[i]-diff[i-1] )\n",
    "                \n",
    "                dp[i][j][1]=min(dp[i][j][1], dp[i-1][j-1][1] )\n",
    "                dp[i][j][1]=min(dp[i][j][1], dp[i-1][j-1][0] )\n",
    "        ans=int(1e9)\n",
    "        for j in range(0,l+1,2):\n",
    "            for last in range(2):\n",
    "                ans=min(ans,dp[l-1][j][last]+x*(j//2))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        n = len(s1)\n",
    "        a = [i for i in range(n) if s1[i] != s2[i]]\n",
    "        m = len(a)\n",
    "\n",
    "        @cache\n",
    "        def g(p, q):\n",
    "            if p > q:\n",
    "                return 0\n",
    "            if p == q:\n",
    "                return math.inf\n",
    "            if p == m-1:\n",
    "                return math.inf\n",
    "            ans = a[p+1] - a[p] + g(p+2, q)\n",
    "            if a[p+1] == a[p]+1:\n",
    "                return ans\n",
    "            for k in range(p+1, q+1):\n",
    "                if k-p >= 3 and (k-p) % 2 and a[k-1] - a[k-2] >= x:\n",
    "                    break\n",
    "                ans = min(ans, x + g(p+1, k-1) + g(k+1, q))\n",
    "            return ans\n",
    "        \n",
    "        ans = g(0, m-1)\n",
    "        return ans if ans < math.inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        n = len(s1)\n",
    "        assert 1 <= n <= 500 \n",
    "        assert n == len(s2)\n",
    "        for i in s1+s2:\n",
    "            assert i in \"01\"\n",
    "        \n",
    "        s = []\n",
    "        self.x = x\n",
    "        for i in range(n):\n",
    "            if s1[i] != s2[i]:\n",
    "                s.append(1)\n",
    "            else:\n",
    "                s.append(0)\n",
    "        \n",
    "        res = self.sea(tuple(s), 0) \n",
    "        if res >= 10**9:\n",
    "            return -1\n",
    "        return res\n",
    "    \n",
    "    @cache\n",
    "    def sea(self, s, flag):\n",
    "        origin_s = copy.copy(s)\n",
    "        s = list(s)\n",
    "        while s and s[-1] == 0:\n",
    "            s.pop() \n",
    "            \n",
    "        if not s :\n",
    "            if not flag:\n",
    "                return 0 \n",
    "            else:\n",
    "                return 10**9\n",
    "        \n",
    "        s.pop()\n",
    "        if 1 not in s:\n",
    "            if flag:\n",
    "                return 0\n",
    "            else:\n",
    "                return 10**9\n",
    "            \n",
    "        # 连续的\n",
    "        s[-1] = s[-1] ^ 1\n",
    "        res = self.sea(tuple(s), flag) + 1\n",
    "        \n",
    "        s[-1] = s[-1] ^ 1\n",
    "        \n",
    "        # 非连续\n",
    "        s = tuple(s)\n",
    "        if flag:\n",
    "            res = min(res, self.sea(s, 0))\n",
    "        else:\n",
    "            res = min(res, self.sea(s, 1) + self.x)\n",
    "        # print(origin_s, flag, res)\n",
    "        return res\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        n = len(s1)\n",
    "        a = [i for i in range(n) if s1[i] != s2[i]]\n",
    "        m = len(a)\n",
    "\n",
    "        @cache\n",
    "        def g(p, q):\n",
    "            if p > q:\n",
    "                return 0\n",
    "            if p == q:\n",
    "                return math.inf\n",
    "            if p == m-1:\n",
    "                return math.inf\n",
    "            ans = a[p+1] - a[p] + g(p+2, q)\n",
    "            if a[p+1] == a[p]+1:\n",
    "                return ans\n",
    "            for k in range(p+1, q+1):\n",
    "                ans = min(ans, x + g(p+1, k-1) + g(k+1, q))\n",
    "            return ans\n",
    "        \n",
    "        ans = g(0, m-1)\n",
    "        return ans if ans < math.inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, k: int) -> int:\n",
    "        n = len(s1)\n",
    "        cnt1 = cnt2 = 0\n",
    "        for x, y in zip(s1, s2):\n",
    "            cnt1 += int(x == '1')\n",
    "            cnt2 += int(y == '1')\n",
    "        if cnt1 % 2 != cnt2 % 2:\n",
    "            return -1\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, j: int, p: int) -> int:\n",
    "            if i == -1:\n",
    "                return 0 if j == 0 and p == 0 else inf\n",
    "            # if (p == 0 and s1[i] == s2[i]) or (p == 1 and s1[i] != s2[i]):\n",
    "            #     return dfs(i - 1, j, 0)\n",
    "            if s1[i] == '0' and p == 0:\n",
    "                x = '0'\n",
    "            elif s1[i] == '0' and p == 1:\n",
    "                x = '1'\n",
    "            elif s1[i] == '1' and p == 0:\n",
    "                x = '1'\n",
    "            else:\n",
    "                x = '0' \n",
    "            if x == s2[i]:\n",
    "                return dfs(i - 1, j, 0)\n",
    "            if j > 0:\n",
    "                return min(dfs(i - 1, j - 1, 0), dfs(i - 1, j + 1, 0) + k, dfs(i - 1, j, 1) + 1)\n",
    "            return min(dfs(i - 1, j + 1, 0) + k, dfs(i - 1, j, 1) + 1)\n",
    "        return dfs(n - 1, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        if s1.count('1') % 2 != s2.count('1') % 2:\n",
    "            return -1\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, j, prev):\n",
    "            if i == -1:\n",
    "                return 0\n",
    "            if s1[i] == s2[i] and not prev:\n",
    "                return dfs(i - 1, j, False)\n",
    "            if s1[i] != s2[i] and prev:\n",
    "                return dfs(i - 1, j, False)\n",
    "            \n",
    "            res = inf\n",
    "            if j > 0:\n",
    "                res = min(res, dfs(i - 1, j - 1, False))\n",
    "            if i > 0:\n",
    "                res = min(res, dfs(i - 1, j, True) + 1)\n",
    "                res = min(res, dfs(i - 1, j + 1, False) + x)\n",
    "            return res\n",
    "        \n",
    "        return dfs(len(s1) - 1, 0, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        \n",
    "        if s1.count('1') % 2 != s2.count('1') % 2:\n",
    "            return -1\n",
    "        @cache\n",
    "        def dfs(i: int, j: int, pre_rev: bool) -> int:\n",
    "            if i < 0:\n",
    "                return inf if j or pre_rev else 0\n",
    "            if (s1[i] == s2[i]) == (not pre_rev):  # 无需反转\n",
    "                return dfs(i - 1, j, False)\n",
    "            res = min(dfs(i - 1, j + 1, False) + x, dfs(i - 1, j, True) + 1)\n",
    "            if j:  # 可以免费反转\n",
    "                res = min(res, dfs(i - 1, j - 1, False))\n",
    "            return res\n",
    "        return dfs(len(s1) - 1, 0, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        n = len(s1)\n",
    "        if s1.count('1')%2!=s2.count('1')%2:\n",
    "            return -1\n",
    "        @cache\n",
    "        def dsf(idx,if_pre,jun_num):\n",
    "            if idx<0:\n",
    "                if not if_pre and not jun_num:\n",
    "                    return 0 \n",
    "                else:\n",
    "                    return inf\n",
    "            # 可以直接跳到下一个的情况,不需要进行判断\n",
    "            if (s1[idx]==s2[idx])==(not if_pre):\n",
    "                return dsf(idx-1,False,jun_num)\n",
    "            res0 = dsf(idx-1,True,jun_num)+1\n",
    "            res1 = dsf(idx-1,False,jun_num+1)+x\n",
    "            res = min(res0,res1)\n",
    "            if jun_num>0:\n",
    "                res = min(res,dsf(idx-1,False,jun_num-1))\n",
    "            return res\n",
    "\n",
    "        return dsf(n-1,False,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        n = len(s1)\n",
    "        if s1.count('1')%2!=s2.count('1')%2:\n",
    "            return -1\n",
    "        @cache\n",
    "        def dsf(idx,if_pre,jun_num):\n",
    "            if idx<0:\n",
    "                if not if_pre and not jun_num:\n",
    "                    return 0 \n",
    "                else:\n",
    "                    return inf\n",
    "            # 可以直接跳到下一个的情况,不需要进行判断 对res 和jun_num没有任何变化，且是最优选择方式\n",
    "            if (s1[idx]==s2[idx])==(not if_pre):\n",
    "                return dsf(idx-1,False,jun_num)\n",
    "            # 需要判断的部分，不确定的部分无论s1[idx]和s2[idx]是否相等都要试\n",
    "            res = dsf(idx-1,True,jun_num)+1 #第二种方式\n",
    "            if s1[idx]!=s2[idx]:\n",
    "                res1 = dsf(idx-1,False,jun_num+1)+x #第一种方式\n",
    "                res = min(res,res1)\n",
    "            if jun_num>0: #消耗免费次数\n",
    "                res = min(res,dsf(idx-1,False,jun_num-1))\n",
    "            return res\n",
    "\n",
    "        return dsf(n-1,False,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        n = len(s1)\n",
    "        # 如果不同的位置个数为奇数则一定不能相等可以先进行判断\n",
    "        cnt = 0\n",
    "        for i,j in enumerate(s1):\n",
    "            cnt += j != s2[i]\n",
    "        if cnt&1:\n",
    "            return -1\n",
    "        if x == 1:\n",
    "            return cnt>>1\n",
    "        # 难道非要记录那些位置换没换吗？\n",
    "        @cache\n",
    "        def dfs(cur=0,cnt=0,hasChange=False):\n",
    "            if cur == n:\n",
    "                return 0\n",
    "            if (s1[cur] == s2[cur]) == (not hasChange):\n",
    "                return dfs(cur+1,cnt,False)\n",
    "            ans = dfs(cur+1,cnt+1,False)+x\n",
    "            ans = min(ans,dfs(cur+1,cnt,True)+1)\n",
    "            if cnt:\n",
    "                ans = min(ans,dfs(cur+1,cnt-1,False))\n",
    "            return ans\n",
    "        return dfs()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        if Counter(s1)['1'] % 2 != Counter(s2)['1'] % 2:\n",
    "            return -1\n",
    "\n",
    "        i = 0\n",
    "        n = len(s1)\n",
    "        '''\n",
    "        i=字符\n",
    "        free=有几次免费反转的机会\n",
    "        preRev=上一个字符翻转\n",
    "        '''\n",
    "        @cache\n",
    "        def dfs(i, free, preRev):\n",
    "            if free < 0:\n",
    "                return inf\n",
    "            \n",
    "            if i == n:\n",
    "                if free == 0 and not preRev:\n",
    "                    return 0\n",
    "                else:\n",
    "                    return inf\n",
    "            \n",
    "            '''\n",
    "            什么都不做\n",
    "            '''\n",
    "            if s1[i] == s2[i] and not preRev:\n",
    "                return dfs(i+1, free, False)\n",
    "\n",
    "            if s1[i] != s2[i] and preRev:\n",
    "                return dfs(i+1, free, False)\n",
    "            \n",
    "            # 第i个位置不相等\n",
    "            if (s1[i] != s2[i] and not preRev) or (s1[i] == s2[i] and preRev):\n",
    "                return min(dfs(i+1, free-1, False), dfs(i+1, free+1, False)+x, dfs(i+1,free,True)+1)\n",
    "            \n",
    "\n",
    "        return dfs(0,0,False)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
